package com.mgq.algorithm.forcerecursive;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author MaGuangQi
 * 给你一个栈,请你逆序这个栈,不能申请额外数据结构.使用递归
 * @date 2022-01-07 13:46
 **/
public class ReverseStack {

    /**
     * f函数的作用是 给一个栈,将栈底的元素返回,同时将栈底的元素删除
     * 不如 1->2->3 删除3,变为 1->2 返回3
     * @param stack
     * @return
     */
    public static int f(Stack<Integer> stack) {
        Integer cur = stack.pop();
        //相当于一直在递归栈,直到找到栈底元素.
        //同时保留当前元素.通过栈把当前元素再压回去.
        if (stack.isEmpty()) {
            return cur;
        }
        int last = f(stack);
        stack.push(cur);
        return last;
    }

    public static void reverseStack(Stack<Integer> stack, List<Integer> result) {
        if (stack.isEmpty()) {
            return;
        }
        //f函数每次删除栈底元素,同时返回栈底元素
        result.add(f(stack)) ;
        System.out.println(result);
        //不停的递归栈
        reverseStack(stack,result);
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(2);
        stack.push(1);
        reverseStack(stack,new ArrayList<>());
    }
}
